package com.honeywen.mymvc.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 143. 重排链表
 * https://leetcode-cn.com/problems/reorder-list/
 *
 * @author wangwei
 * @date 2018/12/26 上午10:22
 */
public class ReorderList {

    public static void main(String[] args) {

        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;

        print(node1);
        print(reorderList(node1));

    }

    private static void print(ListNode node) {

        while (node != null) {
            System.out.print(node.val + "->");

            node = node.next;
        }
        System.out.println();

    }


    public static ListNode reorderList(ListNode head) {

        List<Integer> list = new ArrayList<>();
        ListNode node = head;
        while (node != null) {
            list.add(node.val);
            node = node.next;
        }


        ListNode n = new ListNode(head.val);
        ListNode x = n;
        for (int i = 0, len = list.size(), j = len - i  -1; i < j; i++, j--) {
            ListNode n1 = new ListNode(i);
            ListNode n2 = new ListNode(j);
            n.next = n1;
            n1.next = n2;
            n = n2;



        }

        return x.next;

    }
}
